package _dp

import org.junit.Assert
import org.junit.Test

/*
 https://leetcode.cn/problems/min-cost-climbing-stairs/description/
 https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html

 746. 使用最小花费爬楼梯
 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
 */
class leetcode_746 {
    @Test
    fun test_1() {
        val actual = minCostClimbingStairs(intArrayOf(10, 15, 20))
        val expect = 15
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_2() {
        val actual = minCostClimbingStairs(intArrayOf(1, 100, 1, 1, 1, 100, 1, 1, 100, 1))
        val expect = 6
        Assert.assertEquals(actual, expect)
    }

    fun minCostClimbingStairs(cost: IntArray): Int {
        // 动态规划
        // S - N
        // T - N
        // TODO: cost.size+1
        val dp: IntArray = IntArray(cost.size + 1) // 达到i时所需要的花费
        // 只有开始爬才花费费用
        dp[0] = 0
        dp[1] = 0
        for (i in 2..cost.size) { // TODO：dp:[0,size]
            // 爬一步，或二步，选择最小的那个
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
            println("i-1=> ${dp[i - 1]} + ${cost[i - 1]}")
            println("i-2=> ${dp[i - 2]} + ${cost[i - 2]}")
            println("dp[$i]=${dp[i]}")
        }
        // TODO: cost.size
        return dp[cost.size]
    }
}